package nine.test_9_20;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public int[][] findIntersection (int[][] firstList, int[][] secondList) {
        // write code here
        int i = 0;
        int j = 0;
        List<int[]> result = new ArrayList<>();
        while (i < firstList.length && j < secondList.length) {
            if (i < firstList.length && j < secondList.length && firstList[i][1] < secondList[j][0]) {
                i++;
            }
            if (i < firstList.length && j < secondList.length && firstList[i][0] > secondList[j][1]) {
                j++;
            }
            if(i < firstList.length && j < secondList.length) {
                int start = Math.max(firstList[i][0], secondList[j][0]);
                int end = Math.min(firstList[i][1], secondList[j][1]);
                if (start < end) {
                    result.add(new int[] {start, end});

                }
                if(firstList[i][1] < secondList[j][1]) {
                    i++;
                } else {
                    j++;
                }
            }
        }
        int[][] re = new int[result.size()][2];
        for (int k = 0; k < result.size(); k++) {
            re[k] = result.get(k);
        }
        return  re;
    }

    public int StringSplit (String str) {
        // write code here
        int al = 0;
        int bl = 0;
        int max = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(c == 'b') {
                bl++;
            }
        }
        for (int i = 0; i < str.length() - 1; i++) {
            char c = str.charAt(i);
            if(c == 'b') {
                bl--;
            }
            if (c == 'a') {
                al++;
            }
            int count = al + bl;
            max = Math.max(max,count);
        }
        return max;
    }
    int end;
    HashMap<Integer,Integer> hashMap = new HashMap<>();
    public int numberOfWays (int startPos, int endPos, int k) {
        // write code here
        end = endPos;
        return getResult(startPos,k);
    }
    private int getResult(int sta,int k) {
        int ma = Math.abs(end - sta);
        if((k % 2) != ma % 2 || ma > k) {
            return 0;
        }
        if (ma == k) {
            return 1;
        }
        if (hashMap.containsKey(sta*1001 + k)) {
            return hashMap.get(sta*1001 + k);
        } else {
            int vue = ((getResult(sta + 1,k - 1) + getResult(sta - 1,k - 1))) % (int)(1e9 + 7);
            hashMap.put(sta*1001 + k,vue);
            return vue;
        }
    }
}
